package com.ln.prac.base.xiaoao.dataStructure;

/**
 * 八皇后问题<br/>
 * 棋盘 8*8
 *
 * @Author zhangj
 * @Date 2023/2/5 22:57
 */
public class Equeue {

    int[] queues = new int[8];

    /**
     * 解决每列的摆放
     *
     * @param col
     * @return
     */
    public boolean solve(int col) {
        // 终止条件
        if (col == 8) {
            return true;
        }

        // row: 行
        for (int row = 0; row < 8; row++) {
            queues[col] = row;

            boolean flag = true;

            for (int j = 0; j < col; j++) {
                // rowDiff：行差
                int rowDiff = Math.abs(queues[j] - row);
                // colDiff：列差
                int colDiff = col - j;

                if (rowDiff == colDiff // 行差=列差，说明两个皇后在对角线上
                        || queues[j] == row // 两个皇后在同一个水平线上
                ) {
                    flag = false;
                    break;
                }
            }

            if (flag && solve(col + 1)) {
                return true;
            }
        }

        return false;
    }

    public void print() {
        for (int col = 0; col < 8; col++) {
            for (int row = 0; row < 8; row++) {
                if (queues[col] == row) {
                    System.out.print("Q");
                } else {
                    System.out.print(".");
                }
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        Equeue equeue = new Equeue();
        equeue.solve(0);
        equeue.print();
    }

}
